package Alibaba;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-01-22 15:36
 *
 * 135. 分发糖果
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 * 你需要按照以下要求，给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。
 * 相邻两个孩子评分更高的孩子会获得更多的糖果。
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
 * 贪心：从左到右遍历，当前孩子平方比前一个高时增加1，记为left，同理计算right从右到左
 * 然后每个位置取left和right中的最大值
 */
public class candy135 {
    public int candy(int[] ratings) {
        int n=ratings.length;
        int[] left=new int[n],right=new int[n];
        Arrays.fill(left,1);
        Arrays.fill(right,1);
        for (int i = 1; i < n; i++) {
            left[i]=ratings[i]>ratings[i-1]?left[i-1]+1:1;
            //System.out.println("left="+left[i]);
        }

        int res=left[n-1];
        for (int i = n-2; i >=0 ; i--) {
            right[i]=ratings[i]>ratings[i+1]?right[i+1]+1:1;
            System.out.println("right="+right[i]);
            res+=Math.max(left[i],right[i]);
            System.out.println("res="+res);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] ratings={1,2,87,87,87,2,1};
        candy135 obj=new candy135();
        System.out.println(obj.candy(ratings));
    }
}
